#include<vector>
#include<string>
#include<deque>
#include<unordered_map>
#include<unordered_set>
using namespace std;
class Solution {
private:
    double calcEquationCore(unordered_map<string, vector<pair<string, double>>>& graph, vector<string>& query) {
        auto it1 = graph.find(query[0]);
        auto it2 = graph.find(query[1]);
        if (it1 == graph.end() || it2 == graph.end())
            return -1;
        if (query[0] == query[1])
            return 1.0;
        deque<pair<string, double>> queue;
        queue.push_back(make_pair(query[0], 1.0));
        string target = query[1];
        unordered_set<string> visited;
        visited.insert(query[0]);
        while (!queue.empty()) {
            int size = queue.size();
            while (size > 0) {
                --size;
                auto item = queue.front();
                queue.pop_front();
                for (auto i : graph[item.first]) {
                    if (visited.find(i.first) != visited.end())
                        continue;
                    if (i.first == target) {
                        return item.second * i.second;
                    }
                    i.second *= item.second;
                    queue.push_back(i);
                    visited.insert(i.first);
                }
            }
        }
        return -1;
    }

public:
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        unordered_map<string, vector<pair<string, double>>> graph;
        for (int i = 0; i < equations.size(); ++i) {
            graph[equations[i][0]].emplace_back(equations[i][1], values[i]);
            graph[equations[i][1]].emplace_back(equations[i][0], 1 / values[i]);
        }
        vector<double>res;
        for (auto& query : queries) {
            res.push_back(calcEquationCore(graph, query));
        }
        return res;
    }
};